#
# @lc app=leetcode.cn id=93 lang=python3
#
# [93] 复原 IP 地址
#
# https://leetcode-cn.com/problems/restore-ip-addresses/description/
#
# algorithms
# Medium (55.07%)
# Likes:    795
# Dislikes: 0
# Total Accepted:    183.4K
# Total Submissions: 332.6K
# Testcase Example:  '"25525511135"'
#
# 有效 IP 地址 正好由四个整数（每个整数位于 0 到 255 之间组成，且不能含有前导 0），整数之间用 '.' 分隔。
# 
# 
# 例如："0.1.2.201" 和 "192.168.1.1" 是 有效 IP 地址，但是 "0.011.255.245"、"192.168.1.312"
# 和 "192.168@1.1" 是 无效 IP 地址。
# 
# 
# 给定一个只包含数字的字符串 s ，用以表示一个 IP 地址，返回所有可能的有效 IP 地址，这些地址可以通过在 s 中插入 '.'
# 来形成。你不能重新排序或删除 s 中的任何数字。你可以按 任何 顺序返回答案。
# 
# 
# 
# 示例 1：
# 
# 
# 输入：s = "25525511135"
# 输出：["255.255.11.135","255.255.111.35"]
# 
# 
# 示例 2：
# 
# 
# 输入：s = "0000"
# 输出：["0.0.0.0"]
# 
# 
# 示例 3：
# 
# 
# 输入：s = "1111"
# 输出：["1.1.1.1"]
# 
# 
# 示例 4：
# 
# 
# 输入：s = "010010"
# 输出：["0.10.0.10","0.100.1.0"]
# 
# 
# 示例 5：
# 
# 
# 输入：s = "101023"
# 输出：["1.0.10.23","1.0.102.3","10.1.0.23","10.10.2.3","101.0.2.3"]
# 
# 
# 
# 
# 提示：
# 
# 
# 0 <= s.length <= 20
# s 仅由数字组成
# 
# 
#

# @lc code=start
class Solution:
    class TreeNode:
        def __init__(self, val='-1'):
            self.val = val
            self.children = []
    # construct tree;
    # node must be statisfy: not begin with 0, <=255
    def func(self,s, root):
        # s is the string;
        # root is root node
        if s:
            # not None
            # construct possible tree node
            for step in range(1, 4):
                # step is 1, 2, 3
                # str(int(s[0:step])) == s[0:step] : not start with 0
                # len(s[0:step]) == step : ensure that not empty
                if str(int(s[0:step])) == s[0:step] and int(s[0:step]) <= 255 and len(s[0:step]) == step:
                    newnode = self.TreeNode(s[0:step])
                    root.children.append(newnode)
                    # continue to construct
                    self.func(s[step:], newnode)
    def post_visit(self, root):
        # 类似于后续遍历，需要判定是否全部访问过，需要判定是否是真的叶子节点。
        tree_stack = [root]
        visited_flag = {}
        is_true_leafe = False
        all_path = []
        while tree_stack:
            # 当节点全部弹出，表示遍历结束了。
            current = tree_stack[-1]
            while current.children:
                # 只要有孩子就持续进栈。

                # 本来是要分开写，我这次一块写写试试
                not_visited_children = [child for child in current.children if not visited_flag.get(child, False)]
                # 按照层次顺序访问
                if not_visited_children:
                    # not None
                    # 表示，是去往true_leafe的路上
                    tree_stack.append(not_visited_children[0])
                    current = not_visited_children[0]
                    is_true_leafe = True
                else:
                    is_true_leafe = False
                    break
            # 两种情况
            if is_true_leafe:
                # 这个其实是，来判断路径的，是否是全路径还是中间路径
                # flush the stack
                all_path.append([node.val for node in tree_stack])
            # 不管是那种情况
            # 弹出，并设置为，visited。
            visited_flag[tree_stack.pop()] = True
        # pass
        # 全部访问结束整理路径，返回最终结果。
        return ['.'.join(path[1:]) for path in all_path if len(path) == 5]
    def restoreIpAddresses(self, s: str) -> List[str]:
        # get the treerootnode
        treerootnode = self.TreeNode()
        self.func(s, treerootnode)
        # finish the tree visit
        return self.post_visit(treerootnode)
# @lc code=end

